package com.搜索二叉树;

import com.二叉树2.TreeNode;
import sun.awt.image.ImageWatched;

import java.util.*;
import java.util.concurrent.ScheduledExecutorService;

/**
 * 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
 *
 * 调用 next() 将返回二叉搜索树中的下一个最小的数。
 *
 *  
 *
 * 示例：
 *
 *
 *
 * BSTIterator iterator = new BSTIterator(root);
 * iterator.next();    // 返回 3
 * iterator.next();    // 返回 7
 * iterator.hasNext(); // 返回 true
 * iterator.next();    // 返回 9
 * iterator.hasNext(); // 返回 true
 * iterator.next();    // 返回 15
 * iterator.hasNext(); // 返回 true
 * iterator.next();    // 返回 20
 * iterator.hasNext(); // 返回 false
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/introduction-to-data-structure-binary-search-tree/xpg4qe/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 二叉搜索树迭代器 {
    static  class BSTIterator {
        Queue<Integer> queue ;
        public BSTIterator(TreeNode root) {
            queue = new LinkedList<>();
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || root != null){
                while (root != null){
                    stack.push(root);
                    root = root.left;
                }
                TreeNode pop = stack.pop();
                queue.add(pop.val);
                root = pop.right;
            }
        }

        /** @return the next smallest number */
        public int next() {
            if(!hasNext()){
                return -1;
            }

            return queue.poll();
        }

        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return  !queue.isEmpty();
        }

        public static void main(String[] args) {
            BSTIterator bstIterator = new BSTIterator(new TreeNode(new Integer[]{1,2,3}));
            Scanner scanner = new Scanner(System.in);
            while (true){
                int i = scanner.nextInt();
                switch (i){
                    case 1:
                        System.out.println(bstIterator.hasNext());
                        break;
                    case 2:
                        System.out.println(bstIterator.next());
                        break;
                    case 3:
                        System.exit(1);
                }
            }
        }
    }
}
